Exchange Argument
임의의 인접한 두 원소 x,y에 대해서만 생각했을 때, 그 둘의 순서를 바꿔야 하는지는 간단하게 구할 수 있다. 예를 들어 2180번 소방서의 고민 문제의 경우, x→y 순서로 처리할 경우 x.a*t + x.b + y.a*(t+x.b) + y.b 이고, y→x 순서로 처리할 경우 y.a*t + y.b + x.a*(t+y.b) + x.b이다.
첫번째 식이 더 작을경우 안바꾸는게 이득이므로 부등식을 세우면 y.a*x.b < x.a*y.b 일때 안바꾸는게 이득인 거다. 즉, 올바른 순서인 것이다.
우리는 인접한 두 원소에 대해서만 고려했지만, 정렬은 임의의 두 원소 사이에도 비교가 일관성있어야 가능하다. 즉, Total Ordering이어야 한다.
처음 접근해본 증명은 버블소트가 인접한 두원소끼리만 비교해서 정렬하기 때문에 인접한 두 원소에 대해서만 봐도 된다고 생각해 봤지만 당연히 반례가 있을거 같다.
위에서 찾았던 올바른 순서인지 판별하는 부등식을 한번 더 정리해서 x.b/x.a < y.b/y.a 를 얻을 수 있고, 이는 임의의 두 원소 x, y를 비교할 때 각 원소 z는 일정한 유리수상수(z.b/z.a)와 동일한 순서(=거리)를 갖는다는 시각으로 볼 수 있다. 유리수는 Total Ordering이므로 우리가 찾은 정렬부등식?도 Total Ordering에서 돌아가는 것이고, 따라서 안전하게 정렬할 수 있는 것이다.
이러한 관점에서 인접한 두 원소 x,y에 대해 부등식을 세웠을때, 좌변과 우변을 x에 대한 상수와 y에 대한 상수로 표현할 수 있다면 그 정렬부등식을 기준으로 정렬하고 그리디하게 푸는게 가능한것 같다.
6216번의 공식풀이도 읽어보면 좋을 것이다.
내용추가: 16496번은 정렬함수를 x+y<y+x 로 작성한게 x*INF<y*INF와 동치이기 때문에 저 정렬함수를 사용할 수 있다고 한다. 물론 자릿수 제한이 9로 작아서 INF대신 9를 써도 맞을 수 있다고 하지만 제한이 크면 첫번째 비교함수만 사용할 수 있을테니 생각해보자. 그런데 왜 동치인지는 잘 모르겠다. 종만북의 책장쌓기는 w_i+u_i로 정렬하는 증명이 나오는데 잘 기억안나서 그것도 한번 읽어보자.